Day6 Leetcode Array系列---- Best Time to Buy and Sell StockII

本次題目 Best Time to Buy and Sell Stock II by Ruby

這次的題目與 day5 的相似，只是不再限制交易次數，不能同日買賣，希望再給予的價格波動表中取得最大總獲利

Example 1:

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.
Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

思考路線

1. 首先假裝自己能夠預知未來
2. 買在漲價之前，賣在跌價之前，要能賺到每一個波段
3. 我會需要將每次獲利存在一個變數中 (profit)
4. 可能要考慮手上是否持有股票
5. 有沒有可能都不購買
6. 手中的股票有沒有可能在最後一天都沒賣出去

Coding Time

這邊是題目給的價格波動表與獲利最大值

input1 = [7,1,5,3,6,4]
Output1= 7
input2 = [1,2,3,4,5]
Output2= 4
input3 = [7,6,4,3,1]
Output3= 0

這是我寫的簡單測試，a 就是執行完方法後的結果，b 是題目給的獲利最大值，如果兩者相等就會印出 true ，反之 false

def expect(a, b)
    p a == b
end

先準備好方法，這邊準備 profit 累積每次交易獲利， keep 是買入時的價格，也可以當作是否持有股票的判斷，之後的迴圈是交易日的長度

def max_profit(arr)
    profit = 0
    keep = 0
    for i in [*0..arr.length-1]
        
    end
    return profit
end

我們必須要做到在漲價之前買，跌價之前賣，不能同日買賣，賣出股票必須先在手上持有這些條件，我用 if 來判斷是否符合。

第一個條件是當明天價格比今天低( arr[i+1] < arr[i] )且手上持有股票( keep != 0 ) 我就會今天賣出，這個時候必須考慮如果明天休市怎麼辦，所以把明天必須有價格這個條件也加入( arr[i+1] != nil )

def max_profit(arr)
    profit = 0
    keep = 0
    for i in [*0..arr.length-1]
        if arr[i+1] != nil and arr[i+1] < arr[i] and keep != 0
            profit += arr[i] - keep
            keep = 0
        
        end
    end
    return profit
end

第二個條件，當明天價格大於今天，手上沒有持有股票，今天就買下去！
當然也是要考慮明天有沒有開市，不然沒有比較對象

def max_profit(arr)
    profit = 0
    keep = 0
    for i in [*0..arr.length-1]
        if arr[i+1] != nil and arr[i+1] < arr[i] and keep != 0
            profit += arr[i] - keep
            keep = 0
        elsif arr[i+1] != nil and arr[i+1] >= arr[i] and keep ==0
            keep = arr[i]
        
        end
    end
    return profit
end

最後，有沒有可能手頭上持有股票直到最後一天還沒有賣掉！
當然不行，沒有賣掉就不能成為獲利！
加上最後一條，到最後一天手上有持股就必須賣掉！

def max_profit(arr)
    profit = 0
    keep = 0
    for i in [*0..arr.length-1]
        if arr[i+1] != nil and arr[i+1] < arr[i] and keep != 0
            profit += arr[i] - keep
            keep = 0
        elsif arr[i+1] != nil and arr[i+1] >= arr[i] and keep ==0
            keep = arr[i]
        elsif i == arr.length-1 and keep != 0
            profit += arr[i] - keep
        end
    end
    return profit
end

思考路線----強者

1. 要收集獲利，用 reduce 來收集好了
2. 交易日的時間就用 arr.size -1 來處理吧
3. 要取得 arr 的元素，把index 也抓出來吧
4. 只要去計算每兩天的價差就好了
5. 價差只要是正的都加起來

Coding Time----強者

input1 = [7,1,5,3,6,4]
Output1= 7
input2 = [1,2,3,4,5]
Output2= 4
input3 = [7,6,4,3,1]
Output3= 0

def profit(ary)
  (ary.size - 1).times.reduce(0) do |rs, idx|
    cnt = ary[idx + 1] - ary[idx]
    rs + (cnt > 0 ? cnt : 0)
  end
end

expect = -> (a, b) do       //大大的測試
  rs = profit(a)
  p rs
  p rs == b
end.curry

expect.([7,1,5,3,6,4]).(7)
expect.([1,2,3,4,5]).(4)
expect.([7,6,4,3,1]).(0)

大大不愧是大大

用 while 也可以喔----by 大大

def profit(ary)
  idx = 0
  rs = 0
  while idx < ary.size - 1
    cnt = ary[idx + 1] - ary[idx]
    rs += cnt if cnt > 0
    idx += 1
  end
  rs
end

大大用遞迴搞定了，雖然大大認為遞迴對於閱讀程式碼不太好

def profit(ary, total = 0)
  return total if ary.size <= 1
  
  cnt = ary[1] - ary.shift // shift 是把陣列的第一個元素取出
  profit(ary, total + (cnt > 0 ? cnt : 0))
end

這6天寫了這幾題都還只是 Leecode Array 的 easy 難度，Leecode 的easy 到底是誰訂的，你家的 easy 還真不 easy

今天到此為止，有任何問題請在下方留言或透過email、GitHub聯絡我，感謝閱讀

Daily kitty